using System;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0135. 分发糖果")]
    public class No0135_Candy : AbsBaseTestItem
    {
        /*
        老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
        你需要按照以下要求，帮助老师给这些孩子分发糖果：
            每个孩子至少分配到 1 个糖果。
            相邻的孩子中，评分高的孩子必须获得更多的糖果。
        那么这样下来，老师至少需要准备多少颗糖果呢？

        示例 1:
            输入: [1,0,2]
            输出: 5
            解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
        示例 2:
            输入: [1,2,2]
            输出: 4
            解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
                第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
        */

        public override void OnTest()
        {
            OnExecute(Candy_TwoTraversals);
            OnExecute(Candy_ConstantSpaceTraversal);
        }
        private void OnExecute(Func<int[], int> func)
        {
            Assert.TestExe(func, new int[] { 1, 0, 2 }, 5);
            Assert.TestExe(func, new int[] { 1, 2, 2 }, 4);
        }

        /// <summary>
        ///  方法一：两次遍历
        /// </summary>
        public int Candy_TwoTraversals(int[] ratings)
        {
            int n = ratings.Length;
            int[] num = new int[n];
            for (int i = 0; i < n; i++)
            {
                if (i > 0 && ratings[i - 1] < ratings[i])
                {
                    num[i] = num[i - 1] + 1;
                    continue;
                }
                num[i] = 1;
            }
            int sum = 0;
            for (int i = n - 1; i >= 0; i--)
            {
                if (i > 0 && ratings[i - 1] > ratings[i] && num[i - 1] <= num[i])
                {
                    num[i - 1] = num[i] + 1;
                }
                sum += num[i];
            }
            return sum;
        }

        /// <summary>
        ///  方法二：常数空间遍历
        /// </summary>
        public int Candy_ConstantSpaceTraversal(int[] ratings)
        {
            int n = ratings.Length;
            int ret = 1;
            int inc = 1, dec = 0, pre = 1;
            for (int i = 1; i < n; i++)
            {
                if (ratings[i] >= ratings[i - 1])
                {
                    dec = 0;
                    pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                    ret += pre;
                    inc = pre;
                }
                else
                {
                    dec++;
                    if (dec == inc)
                    {
                        dec++;
                    }
                    ret += dec;
                    pre = 1;
                }
            }
            return ret;
        }
    }
}
